package digui;

import java.util.ArrayList;
import java.util.List;

public class Test1 {
    //题目 :力扣 面试题08.06汉诺塔问题
    //算法 : 递归解决
    public static void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        //直接用递归  解决  每次都要借助一个东西来转移 相同的子问题
        int n = A.size();
        move(A,B,C,n);
    }
    public static void move(List<Integer> A,List<Integer> B,List<Integer> C,int n) {
        if(n == 1) {
            C.add(A.remove(A.size()-1));
            return;
        }

        move(A,C,B,n-1);
        C.add(A.remove(A.size()-1));
        move(B,A,C,n -1);
    }

    public static void main(String[] args) {
        List<Integer> listA = new ArrayList<>(3);
        List<Integer> listB = new ArrayList<>();
        List<Integer> listC = new ArrayList<>();
        hanota(listA,listB,listC);
    }
}
